package facebook;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Collection;
import java.util.LinkedList;


public class Decode1 {

	public static class Trie {
		private TrieNode root;

		public Trie() {
			root = new TrieNode(' ');
		}

		public void insert(String s) {
			TrieNode current = root;
			if (s.length() == 0)
				current.isLeaf = true;
			for (int i = 0; i < s.length(); i++) {
				TrieNode child = current.subNode(s.charAt(i));
				if (child != null) {
					current = child;
				} else {
					current.child.add(new TrieNode(s.charAt(i)));
					current = current.subNode(s.charAt(i));
				}
				if (i == s.length() - 1)
					current.isLeaf = true;
			}
		}

		public int is_word(String s) {
			TrieNode current = root;
			while (current != null) {
				for (int i = 0; i < s.length(); i++) {
					if (current.subNode(s.charAt(i)) == null)
						return 0;
					else
						current = current.subNode(s.charAt(i));
				}
				if (current.isLeaf == true)
					return 1;
				else
					return 2;
			}
			return 0;
		}
	}
	
	public static class TrieNode {
		char content;
		boolean isLeaf;
		Collection<TrieNode> child;

		public TrieNode(char c) {
			child = new LinkedList<TrieNode>();
			isLeaf = false;
			content = c;
		}

		public TrieNode subNode(char c) {
			if (child != null) {
				for (TrieNode eachChild : child) {
					if (eachChild.content == c) {
						return eachChild;
					}
				}
			}
			return null;
		}

	}
	
	private static Trie trie = new Trie();
	
	//for simplicity I put all the dictionary words into a file called dict.txt
	//and construct a trie out of all the words in that dictionary
	public static void constrDict(){
		try {
			BufferedReader br = new BufferedReader(new FileReader("./dict.txt"));
			String line = "";
			while((line = br.readLine()) != null){
				trie.insert(line);
			}
		} catch (Exception e) {
			System.out.println("Exception happned when construct the dictionary trie");
			e.printStackTrace();
		}
	}
	
	//this array contains the mapping of integer to characters
	//for simplicity, i assume that all the  characters in the words in the dictionary are lower case
	private static String[] mapping = { "afkpuz", "bglqv", "chmrw", "dinsx",
			"ejoty" };
	
	

	public static void decode(String message) {
		constrDict();
		int[] num = new int[message.length()];
		for (int i = 0; i < num.length; i++) {
			num[i] = message.charAt(i) - 49;
			if(num[i] > 5 || num[i] < 0){
				System.out.println("invalid number in the message");
				return;
			}
		}
		int n = num.length;
		int answer[] = new int[n];
		while (true) {
			if(trie.is_word(getResult(num, answer, n-1)) == 1)
				System.out.println(getResult(num, answer, n - 1));
			int k = n - 1;
			while (k >= 0) {
				answer[k]++;
				while (answer[k] <= mapping[num[k]].length() - 1 && trie.is_word(getResult(num, answer, k)) == 0) {
					answer[k]++;
				} 
				if(answer[k] <= mapping[num[k]].length() - 1)
					break;
				else {
					answer[k] = 0;
					k--;
				}
			}
			if (k < 0)
				break;
		}
	}
	
	private static String getResult(int[] telNum, int[] answer, int k){
		StringBuilder result = new StringBuilder();
		for (int i = 0; i <= k; i++)
			result.append(mapping[telNum[i]].charAt(answer[i]));
		return result.toString();
	}

	
	public static void main(String[] args) {
		String message = "2545";
		Decode1.decode(message);
	}

}
